This invention relates to an arithmetic processor, and more particularly to an arithmetic processor particularly suitable for repeated high speed execution of arithmetic operations.
A conventional high speed multiplier has been described, for example, in pages 76 to 90 of Nikkei Electronics, May 29, 1978. In a binary array multiplier or a multiplier using a Wallace tree, partial products are summed up by using a carry save adder to obtain a product represented in a carry save expression (two binary numbers), and the product is converted into an ordinary binary number by using a carry look ahead adder or the like. In these multipliers, the amount of hardware is decreased and the computation speed is increased by reducing the number of partial products by one-half by converting the multipliers into the radix 4 signed-digit numbers consisting of elements of -2, -1, 0, 1, 2 by the 2-bit Booth method.
A high speed binary multiplier using a redundant binary addition tree is discussed in pages 683 to 690 of Trans. of IECE Japan, Vol. J66-D, No. 6 (1983). In this multiplier, a redundant binary expression consisting of elements -1, 0, 1 (that is, a signed digit expression) is used in the arithmetic operation. In n-bit multiplication, n partial products are regarded as redundant binary numbers, and are added, two by two, in the redundant binary number system in a twin tree form, and the product determined by converting the redundant binary expression into an ordinary binary expression. In the redundant binary number system, addition of two numbers can be done in a constant time, regardless of the number of digits involved in the arithmetic operation, without carry propagation. Therefore, in the multiplier using the redundant binary addition tree, an n-bit multiplication can be accomplished at a high speed in computation time O (log n). The computation speed is as fast as that of the high speed multiplier using the Wallace tree, being considerably higher than that of the conventional array multiplier. In addition, the circuit structure is as regular as that of the array multiplier, and the layout is simpler than the layout of the multiplier using the Wallace tree.
The method of realizing division and extraction of the square roots using an arithmetic processor possessing a redundant binary multiplier is discussed in pages 45 to 50 of Report of IECE Japan, AL85-90 (March 1986). In this method, it is necessary to multiply redundant binary members mutually in the multiplier. When the multiplier is configured to multiply redundant binary numbers, the quantity of hardware increases, compared with the multiplier for mutual binary numbers.